package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printLevelOrder

/**
 *

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
题型：二叉树的前序遍历、后序遍历，分割数组

105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。


示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
 */
class leetcode_105 {
    @Test
    fun test_1() {
        val root = buildTree(intArrayOf(3,9,20,15,7), intArrayOf(9,3,15,20,7))
        val actual = printLevelOrder(root)
        val expect = arrayListOf(arrayListOf(3), arrayListOf(9, 20), arrayListOf(15, 7))
        Assert.assertEquals(expect.toString(), actual.toString())
    }


    @Test
    fun test_2() {
        val root = buildTree(intArrayOf(-1), intArrayOf(-1))
        val actual = printLevelOrder(root)
        val expect = arrayListOf(arrayListOf(-1))
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
        // T - N的平方
        // S - N

        // 前序数组
        // 中序数组
        // 第1步：后序数组的大小为0，则为空节点。返回它
        // 第2步：取前序数组的第个元素作为节点。如果size 为1，则返回该节点
        // 第3步：找到前序数组的第一个元素在中序数组的位置，作为切割点
        // 第4步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
        // 第5步：切割前序数组，切成后序左数组和后序右数组
        // 第6步：递归处理左区间和右区间
        // 注意区间的闭合：使用[)

        // 简写
        // step 1 : size 0
        // step 2 ：head = 前序数组[0] (size 1 or > 1）
        // step 3 : index head at 中序
        // step 4 : 切割中序数组
        // step 5 : 切割前序数组
        // step 6 ： 递归处理左右区间

        // step 1 : size 0
        if (preorder.size == 0) { // TODO:这一点不同
            return null
        }
        // step 2 ：head = 前序序数组[0] (if size 1 return）
        val n: Int = preorder[0] // TODO:这一点不同
        val node = TreeNode(n)
        println("root=${n}")
        if (preorder.size == 1) {
            println()
            return node
        }

        // step 3 : index head at 中序
        var index: Int = 0
        for (i in 0..inorder.size - 1) {
            if (inorder[i] == n) {
                index = i
                break
            }
        }
        println("index=${index}")

        // step 4 : 切割中序数组
        val left1: IntArray = inorder.sliceArray(0 until index) // [0, index)
//        println("left1=${left1.contentToString()}")
        val right1: IntArray = inorder.sliceArray(index + 1 until inorder.size)  // [index + 1, size)
//        println("right1=${right1.contentToString()}")

        // step 5 : 切割前序序数组
        // 删除前序的第一个元素
        var preorder: IntArray = preorder.sliceArray(1 until preorder.size) //  [1, size) TODO:这一点不同
        val left2: IntArray = preorder.sliceArray(0 until left1.size) //  [0, leftInorder.size)
//        println("left2=${left2.contentToString()}")
        val right2: IntArray = preorder.sliceArray(left1.size until preorder.size) // [leftInorder.size(), size)
//        println("right2=${right2.contentToString()}")
        println()

        // step 6 ： 递归处理左右区间
//        node.left = buildTree(left2, left1) // TODO:这一点不同
//        node.right = buildTree(right2, right1)  // TODO:这一点不同
        node.left = buildTree(left2, left1) // TODO:这一点不同
        node.right = buildTree(right2, right1)  // TODO:这一点不同
        return node
    }
}